package ljl.alg.wangzheng_camp.round1.bisection;

/**
 * 这可真是一个好题！
 *
 * */
public class _875_min_eating_speed {
    
    /**
     * 抄，提交，错了好几次，错哪了？
     *
     * if (time(piles, mid) <= h) 中的 h 写成了 high，
     * 也就是说脑子完全不思考了，为啥会和 high 比呢？
     *
     * 还一个原因，h 和 high 名字起的比较像，感觉上都是 high
     * 不如换个名字叫 upper，lower
     * */
    public int minEatingSpeed(int[] piles, int h) {
        int low = 1, high = 0;
        for (int pile : piles) {
            if (high < pile) high = pile;
        }
        while (low < high) {
            int mid = (low + high) >>> 1;
            if (time(piles, mid) <= h) high = mid;
            else low = mid + 1;
        }
        return low;
    }
    int time(int[] piles, int speed) {
        int time = 0;
        for (int pile : piles) {
            time += (pile - 1) / speed + 1;
        }
        return time;
    }
    
    class official {
        
        public int minEatingSpeed2(int[] piles, int h) {
            int low = 1;
            int high = 0;
            for (int pile : piles) {
                high = Math.max(high, pile);
            }
            while (low < high) {
                int mid = (high - low) / 2 + low;
                if (getTime(piles, mid) <= h) {
                    high = mid;
                } else {
                    low = mid + 1;
                }
            }
            return low;
        }
    
        public long getTime(int[] piles, int speed) {
            long time = 0;
            for (int pile : piles) {
                time += (pile - 1) / speed + 1;
            }
            return time;
        }
    }
}
